import java.util.Arrays;

/**
 * @author zyj
 * @date 2022年05月25日 10:00
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {1, 4, 6, 2, 0, 7, 9, -1, -3, -5, 0, 5, 87};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    private static void quickSort(int[] arr, int start, int end) {
        if (start < end) {
            int index = getIndex(arr, start, end);
            quickSort(arr, start, index - 1);
            quickSort(arr, index + 1, end);
        }

    }

    private static int getIndex(int[] arr, int start, int end) {
        int num = arr[start];
        while (start < end) {
            //从后往前找第一个比基数小的 arr[end] < num
            while (start < end && num <= arr[end]) {
                end--;
            }

            if (start < end) {
                arr[start] = arr[end];
                start++;
            }

            //从前往后找比基数大于等于  arr[start] >= num
            while (start < end && num > arr[start]) {
                start++;
            }


            if (start < end) {
                arr[end] = arr[start];
                end--;
            }
        }
        arr[start] = num;

        return start;
    }
}
